from collections import deque
from typing import List


def plusONe(x: str, i: int) -> str:
    ch = list(x)
    if ch[i] == '9':
        ch[i] = '0'
    else:
        ch[i] = str(int(ch[i]) + 1)
    return "".join(ch)


def minusOne(x: str, i: int) -> str:
    ch = list(x)
    if ch[i] == '0':
        ch[i] = '9'
    else:
        ch[i] = str(int(ch[i]) - 1)

    return "".join(ch)


class Solution:

    def openLock(self, deadends: List[str], target: str) -> int:
        deads = deque(deadends)
        visited = set()
        queue = deque()
        step = 0
        queue.append("0000")
        visited.add("0000")
        while queue:
            size = len(queue)
            for _ in range(size):
                cur = queue.popleft()
                if cur in deads:
                    continue
                if cur == target:
                    return step
                for i in range(4):
                    up = plusONe(cur, i)
                    if up not in visited:
                        queue.append(up)
                        visited.add(up)
                    down = minusOne(cur, i)
                    if down not in visited:
                        queue.append(down)
                        visited.add(down)
            step += 1
        return -1

if __name__ == "__main__":
    solution = Solution()
    step = solution.openLock(["0201","0101","0102","1212","2002"], "0202")
    print(step)